﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
//
using InterfaceLibrary;

namespace QuickSort
{
    /*
     *  QuickSort algorithm
     *  source: http://en.csharp-online.net/Quick_Sort 
     *  
     *  Implemented as it's own library with minimal changes from
     *  original definition. Comments edited and/or added by 
     *  David Boarman.
     * **/
    public class QuickSorter : ISorter
    {
        #region Fields
        //  Fields

        int[] array;
        #endregion

        #region Constructors
        //  Constructors

        /// <summary>
        /// Constructor requires an array of Type int.
        /// </summary>
        /// <param name="Source">Source collection</param>
        public QuickSorter ( int[] Source )
        {
            //  create independent copy of array
            array = new int[ Source.Length ];
            Source.CopyTo ( array, 0 );
        }
        #endregion

        #region Functions
        //  Functions

        #region ISorter Members

        public void Sort ( )
        {
            Sort(0, array.Length - 1);
        }

        #endregion

        /// <summary>
        /// Begin sort routine at given left and right indexes.
        /// </summary>
        /// <param name="Left">Left index at which sorting begins.</param>
        /// <param name="Right">Right index at which sorting ends.</param>
        public void Sort ( int Left, int Right )
        {
            int left = Left;
            int right = Right;

            int pivotPoint = array[(int)((Left + Right) / 2)];

            // Loop
            while (left <= right)
            {
                while (array[left] < pivotPoint)
                {
                    left++;
                }

                while (array[right] > pivotPoint)
                {
                    right--;
                }

                if (left <= right)
                {
                    int temp = array[left];

                    array[left] = array[right];
                    left++;

                    array[right] = temp;
                    right--;
                }
            }

            // Swap
            if (Left < right)
            {
                Sort( Left, right);
            }

            if (left < Right)
            {
                Sort(left, Right);
            } 
        }

        #endregion

        #region Properties
        //  Properties

        public IEnumerable<int> SortedList
        {
            get { return array; }
        }

        #endregion
    }
}
